package com.cqs.leetcode.backtrack;

import java.util.*;

/**
 * @author lixiaowen
 * @create 2019-12-15
 */
public class NQueens51 {





    /**
     * 列放置情况
     */
    private int[] col;
    /**
     * "/"对角线情况
     * 特点：每条“/”对角线相加均是同一常数，不同的对角线之和不同
     * 一共有2×n-1条
     */
    private int[] cross;
    /**
     * 每条“/”对角线坐标相是同一常数，不同的对角线之差不同
     * 因为存在负数，为了方便处理使用set存储
     */
    private Set<Integer> cross2 = new HashSet<>();

    /**
     * 保存每一行的皇后放置情况
     */
    private char[] lineChars;
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        lineChars = new char[n];
        for (int i = 0; i < n; i++) {
            lineChars[i] = '.';
        }
        col = new int[n];
        cross = new int[2 * n - 1];
        totalNQueens(n, 0,result, new ArrayList<>());
        return result;
    }


    public void totalNQueens(final int n,  int level,List<List<String>> result,List<String> list){
        if (level == n){
            result.add(new ArrayList<>(list));
            return;
        }
        //第level行，挨列放值
        for (int i = 0; i < n; i++) {
            //处理列
            if (col[i] == 1) continue;
            // "/"对角线检测
            if (cross[level + i] == 1) continue;
            // "\"对角线
            if (cross2.contains(level - i)) continue;
            col[i] = 1;
            cross[level + i] = 1;
            cross2.add(level - i);
            //
            char[] line = Arrays.copyOf(lineChars, n);
            line[i] = 'Q';
            list.add(new String(line));
            totalNQueens(n, level + 1,result,list);
            //撤销状态
            col[i] = 0;
            cross[level + i] = 0;
            cross2.remove(level - i);
            list.remove(list.size()-1);
        }
    }



    public List<List<String>> solveNQueens_1(int n) {
        List<List<String>> lists = new ArrayList<>();
        byte[][] queens = new byte[n][n];
        List<String> list = new ArrayList<>();
        findQueens(queens,0,n, list,lists);
        return lists;
    }

    private void findQueens(byte[][] queens,final int level,final int n,final List<String> list,List<List<String>> lists) {
        //递归
        if (level == n) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int col = 0; col < n; col++) {
            //列已经有皇后
            int row = level - 1;
            while (row >=0  && queens[row][col] == 0){
                --row;
            }
            //该列已经有皇后
            if (row >= 0) continue;
            //"\对角线" 特点： 下面的元素坐标比上一元素大1
            row = level - 1; int colTmp = col - 1;
            while (row >= 0 && colTmp>= 0 && queens[row][colTmp] == 0) {
                --row;
                --colTmp;
            }
            if (row >= 0 && colTmp >=0) continue;
            // 处理“/”对角线
            row = level -1; colTmp = level + col - row;
            while (row>=0 && colTmp < n && queens[row][colTmp] == 0 ){
                colTmp = level + col - (--row);
            }
            if (row>=0 && colTmp < n) continue;
            queens[level][col] = 1;
            //添加元素
            StringBuilder sb= new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == col) {
                   sb.append("Q");
                }else{
                   sb.append(".");
                }
            }
            list.add(sb.toString());
            findQueens(queens, level + 1, n, list, lists);
            //回溯
            queens[level][col] = 0;
            list.remove(list.size()-1);
        }
    }

    private void println(byte[][] arr){
        for (int i = 0; i <arr.length ; i++) {
            System.out.print("[");
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println("]");
        }
        System.out.println("------------");
    }

    /**
     * 可以找到一个可行解
     *
     * @param column
     * @param level
     * @param n
     * @param list
     */
    private void findQueens(byte[] column,final int level,final int n,final List<String> list) {
        if (level == n) return;
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < n && column[i] == 1) {
            i++;
            sb.append(".");
        }

        if (i == n) {
            return;
        }

        //放置皇后
        column[i] = 1;
        sb.append("Q");
        for (int j = i + 1; j < n; j++) {
            sb.append(".");
        }
        list.add(sb.toString());
//        System.out.println(list);
        findQueens(column, level + 1, n, list);
    }

    public static void main(String[] args) {

        NQueens51 nQueens = new NQueens51();
        List<List<String>> lists = nQueens.solveNQueens(8);
        System.out.println(lists.size());
    }
}
